{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reconstruct Original Digits from English"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: originalDigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从英文中重建数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，其中包含字母顺序打乱的用英文单词表示的若干数字（<code>0-9</code>）。按 <strong>升序</strong> 返回原始的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"owoztneoer\"\n",
    "<strong>输出：</strong>\"012\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"fviefuro\"\n",
    "<strong>输出：</strong>\"45\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>[\"e\",\"g\",\"f\",\"i\",\"h\",\"o\",\"n\",\"s\",\"r\",\"u\",\"t\",\"w\",\"v\",\"x\",\"z\"]</code> 这些字符之一</li>\n",
    "\t<li><code>s</code> 保证是一个符合题目要求的字符串</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reconstruct-original-digits-from-english](https://leetcode.cn/problems/reconstruct-original-digits-from-english/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reconstruct-original-digits-from-english](https://leetcode.cn/problems/reconstruct-original-digits-from-english/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"owoztneoer\"', '\"fviefuro\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        count=collections.Counter(s)\n",
    "        out={}\n",
    "         # letter \"z\" is present only in \"zero\"\n",
    "        out[\"0\"] = count[\"z\"]\n",
    "        # letter \"w\" is present only in \"two\"\n",
    "        out[\"2\"] = count[\"w\"]\n",
    "        # letter \"u\" is present only in \"four\"\n",
    "        out[\"4\"] = count[\"u\"]\n",
    "        # letter \"x\" is present only in \"six\"\n",
    "        out[\"6\"] = count[\"x\"]\n",
    "        # letter \"g\" is present only in \"eight\"\n",
    "        out[\"8\"] = count[\"g\"]\n",
    "        # letter \"h\" is present only in \"three\" and \"eight\"\n",
    "        out[\"3\"] = count[\"h\"] - out[\"8\"]\n",
    "        # letter \"f\" is present only in \"five\" and \"four\"\n",
    "        out[\"5\"] = count[\"f\"] - out[\"4\"]\n",
    "        # letter \"s\" is present only in \"seven\" and \"six\"\n",
    "        out[\"7\"] = count[\"s\"] - out[\"6\"]\n",
    "        # letter \"i\" is present in \"nine\", \"five\", \"six\", and \"eight\"\n",
    "        out[\"9\"] = count[\"i\"] - out[\"5\"] - out[\"6\"] - out[\"8\"]\n",
    "        # letter \"n\" is present in \"one\", \"nine\", and \"seven\"\n",
    "        out[\"1\"] = count[\"n\"] - out[\"7\"] - 2 * out[\"9\"]\n",
    "        \n",
    "        output=[key*out[key] for key in sorted(out.keys())]\n",
    "        return \"\".join(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        # 既然保证了符合题目要求, 首先创建一个字典和英文单词对应:\n",
    "        # 可以发现，z, w, u, x, g 都只在一个数字中，即 0,2,4,6,8 中出现。\n",
    "        # 因此我们可以使用一个哈希表统计每个字母出现的次数，那么 z, w, u, x, g 出现的次数，即分别为 0,2,4,6,8 出现的次数。\n",
    "        # 当我们统计完每个数字出现的次数后，我们按照升序将它们进行拼接即可。\n",
    "\n",
    "        # 原来是文字游戏, 那么如果我说我是学日语的呢? \n",
    "        c = Counter(s)\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = collections.Counter(s)\n",
    "\n",
    "        res = [0]*10\n",
    "        \n",
    "        res[8] = c['g']\n",
    "        res[3] = c['h'] - res[8]\n",
    "        \n",
    "        res[0] = c['z']\n",
    "        res[2] = c['w']\n",
    "        res[6] = c['x']\n",
    "        res[7] = c['s'] - res[6]\n",
    "        res[4] = c['u']\n",
    "        res[5] = c['f'] - res[4]\n",
    "\n",
    "        res[9] = c['i'] - res[5] - res[6] - res[8]\n",
    "        res[1] = c['n'] - res[7] - res[9]*2\n",
    "\n",
    "\n",
    "        return ''.join([str(i)*res[i] for i in range(10) if res[i]!=0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        hash = {}\n",
    "        for i in s:\n",
    "            if hash.get(i, None) == None:\n",
    "                hash[i] = 1\n",
    "            else:\n",
    "                hash[i] += 1\n",
    "        # print('hash:',hash)\n",
    "\n",
    "        lst = {'zero':'0','two':'2','four':'4','six':'6','eight':'8',\n",
    "            'one':'1','three':'3','five':'5','seven':'7','nine':'9'}\n",
    "\n",
    "        for i,j in lst.items():\n",
    "            keylst = list(i)\n",
    "            # print('--------')\n",
    "            # print(keylst)\n",
    "            elst = [hash.get(e,False) for e in keylst]\n",
    "            # print(elst)\n",
    "            if False not in elst:\n",
    "                p = min(elst)\n",
    "                res += j * int(p)\n",
    "                for k in keylst:\n",
    "                    hash[k] -= p\n",
    "                # print(res)\n",
    "\n",
    "        # print('res:',''.join(sorted(res)))\n",
    "        return ''.join(sorted(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        def lt423(s):\n",
    "            d=defaultdict(int)\n",
    "            for ch in s:d[ch]+=1\n",
    "            rec=[0]*10\n",
    "            rec[0]=d['z']\n",
    "            rec[2]=d['w']\n",
    "            rec[4]=d['u']\n",
    "            rec[5]=d['f']-rec[4]\n",
    "            rec[6]=d['x']\n",
    "            rec[7]=d['s']-rec[6]\n",
    "            rec[8]=d['g']\n",
    "            rec[3]=d['h']-rec[8]\n",
    "            rec[9]=d['i']-rec[8]-rec[6]-rec[5]\n",
    "            rec[1]=d['o']-rec[0]-rec[2]-rec[4]\n",
    "            return ''.join([str(i)*rec[i] for i in range(10)])\n",
    "        return lt423(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "num = [\"zero\", \"one\", 'two', \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\"]\n",
    "m = {a: str(i) for i, a in enumerate(num)}\n",
    "\n",
    "\n",
    "@cache\n",
    "def getC(s):\n",
    "    return Counter(s)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        res = []\n",
    "\n",
    "        def check(mid, n):\n",
    "            for k, v in n.items():\n",
    "                if c[k] < v * mid:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for n in  [\"six\",\"eight\",  'two',   \"three\", \"four\",\"zero\", \"one\",  \"five\",  \"seven\", \"nine\"]:\n",
    "            left = -1\n",
    "            right = len(s) + 1\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if check(mid, getC(n)):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "                \n",
    "            print(left, n)\n",
    "            for k, v in getC(n).items():\n",
    "                c[k] -= left * v\n",
    "            res += [m[n]] * left\n",
    "        res.sort()\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        char_count = {}\n",
    "        for char in s:\n",
    "            if char not in char_count:\n",
    "                char_count[char] = 1\n",
    "            else:\n",
    "                char_count[char] += 1\n",
    "\n",
    "        digit_mapping = {\n",
    "            'z': ('0', 'zero'),\n",
    "            'w': ('2', 'two'),\n",
    "            'u': ('4', 'four'),\n",
    "            'x': ('6', 'six'),\n",
    "            'g': ('8', 'eight'),\n",
    "            'o': ('1', 'one'),\n",
    "            'h': ('3', 'three'),\n",
    "            'f': ('5', 'five'),\n",
    "            's': ('7', 'seven'),\n",
    "            'i': ('9', 'nine'),\n",
    "        }\n",
    "\n",
    "        result = []\n",
    "        for char, (digit, word) in digit_mapping.items():\n",
    "            count = char_count.get(char, 0)\n",
    "            if count > 0:\n",
    "                result.append(digit * count)\n",
    "                for c in word:\n",
    "                    char_count[c] -= count\n",
    "\n",
    "        return ''.join(sorted(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c['z']\n",
    "        cnt[2] = c['w']\n",
    "        cnt[4] = c['u']\n",
    "        cnt[6] = c['x']\n",
    "        cnt[8] = c['g']\n",
    "        cnt[1] = c['o'] - cnt[0] - cnt[2] - cnt[4]\n",
    "        cnt[3] = c['t'] - cnt[2] - cnt[8]\n",
    "        cnt[5] = c['f'] - cnt[4]\n",
    "        cnt[7] = c['s'] - cnt[6]\n",
    "        cnt[9] = c['i'] - cnt[5] - cnt[6] - cnt[8]\n",
    "        ans = ''\n",
    "        for i in range(10):\n",
    "            ans += cnt[i] * str(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num=[0]*10\n",
    "        n1={'z':0,'w':2,'u':4,'x':6,'g':8,'o':1,'r':3,'f':5,'v':7,'i':9}\n",
    "        digit=''\n",
    "        for x in s:\n",
    "          if x in n1:\n",
    "           num[n1[x]]+=1\n",
    "        num[1]-=num[0]+num[4]+num[2]\n",
    "        num[3]-=num[4]+num[0]\n",
    "        num[5]-=num[4]\n",
    "        num[7]-=num[5]\n",
    "        num[9]-=num[8]+num[5]+num[6]\n",
    "        for i in range(len(num)):\n",
    "          digit+=str(i)*num[i]\n",
    "        return digit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        s=Counter(s)\n",
    "        ret=[]\n",
    "        def f(key,word,num):\n",
    "            if key in s and s[key]!=0:\n",
    "                cnt=s[key]\n",
    "                for char,val in Counter(word).items():\n",
    "                    s[char]-=cnt*val\n",
    "                ret.append([num,cnt])\n",
    "        f('x','six',6)\n",
    "        f('z','zero',0)\n",
    "        f('s','seven',7)\n",
    "        f('u','four',4)\n",
    "        f('r','three',3)\n",
    "        f('w','two',2)\n",
    "        f('o','one',1)\n",
    "        f('f','five',5)\n",
    "        f('t','eight',8)\n",
    "        f('e','nine',9)\n",
    "        ret.sort()\n",
    "        ans=''\n",
    "        for key,num in ret:\n",
    "            ans+=str(key)*num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        count = [0] * 26  # 用于记录每个字符出现的次数\n",
    "        digit_count = [0] * 10  # 用于记录每个数字出现的次数\n",
    "\n",
    "        # 统计每个字符出现的次数\n",
    "        for char in s:\n",
    "            count[ord(char) - ord('a')] += 1\n",
    "\n",
    "        # 根据题目规则，计算每个数字出现的次数\n",
    "        digit_count[0] = count[ord('z') - ord('a')]  # 'z' 只出现在 \"zero\" 中\n",
    "        digit_count[2] = count[ord('w') - ord('a')]  # 'w' 只出现在 \"two\" 中\n",
    "        digit_count[4] = count[ord('u') - ord('a')]  # 'u' 只出现在 \"four\" 中\n",
    "        digit_count[6] = count[ord('x') - ord('a')]  # 'x' 只出现在 \"six\" 中\n",
    "        digit_count[8] = count[ord('g') - ord('a')]  # 'g' 只出现在 \"eight\" 中\n",
    "        digit_count[1] = count[ord('o') - ord('a')] - digit_count[0] - digit_count[2] - digit_count[4]  # 'o' 出现在 \"one\", \"zero\", \"two\", \"four\" 中\n",
    "        digit_count[3] = count[ord('h') - ord('a')] - digit_count[8]  # 'h' 出现在 \"three\", \"eight\" 中\n",
    "        digit_count[5] = count[ord('f') - ord('a')] - digit_count[4]  # 'f' 出现在 \"five\", \"four\" 中\n",
    "        digit_count[7] = count[ord('s') - ord('a')] - digit_count[6]  # 's' 出现在 \"seven\", \"six\" 中\n",
    "        digit_count[9] = count[ord('i') - ord('a')] - digit_count[5] - digit_count[6] - digit_count[8]\n",
    "\n",
    "        # 构造结果字符串\n",
    "        result = ''.join(str(i) * digit_count[i] for i in range(10))\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        a=[0]*10\n",
    "        b=str()\n",
    "        ss=Counter(s)\n",
    "        for k,v in ss.items():\n",
    "            if k=='z':\n",
    "                a[0]=v\n",
    "                ss['o']-=v\n",
    "            elif k=='w':\n",
    "                a[2]=v\n",
    "                ss['t']-=v\n",
    "                ss['o']-=v\n",
    "            elif k=='x':\n",
    "                a[6]=v\n",
    "                ss['s']-=v\n",
    "            elif k=='u':\n",
    "                a[4]=v\n",
    "                ss['f']-=v\n",
    "                ss['o']-=v\n",
    "            elif k=='g':\n",
    "                a[8]=v\n",
    "                ss['t']-=v\n",
    "\n",
    "        for k,v in ss.items():\n",
    "            if k=='o' and v!=0:\n",
    "                a[1]=v\n",
    "                ss['n']-=v\n",
    "            elif k=='t' and v!=0:\n",
    "                a[3]=v\n",
    "            elif k=='s' and v!=0:\n",
    "                a[7]=v\n",
    "                ss['n']-=v\n",
    "            elif k=='f' and v!=0:\n",
    "                a[5]=v\n",
    "        for k,v in ss.items():\n",
    "            if k=='n':\n",
    "                a[9]=int(v/2)\n",
    "                break\n",
    "        for i in range(10):\n",
    "            b+=str(i)*a[i]\n",
    "        return b\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        hash = {}\n",
    "        for i in s:\n",
    "            if hash.get(i, None) == None:\n",
    "                hash[i] = 1\n",
    "            else:\n",
    "                hash[i] += 1\n",
    "        # print('hash:',hash)\n",
    "\n",
    "        lst = {'zero':'0','two':'2','four':'4','six':'6','eight':'8',\n",
    "            'one':'1','thre':'3','five':'5','sevn':'7','nie':'9'}\n",
    "\n",
    "        for i,j in lst.items():\n",
    "            keylst = list(i)\n",
    "            # print('--------')\n",
    "            # print(keylst)\n",
    "            elst = [hash.get(e,False) for e in keylst]\n",
    "            # print(elst)\n",
    "            if False not in elst:\n",
    "                p = min(elst)\n",
    "                res += j * int(p)\n",
    "                for k in keylst:\n",
    "                    hash[k] -= p\n",
    "                # print(res)\n",
    "\n",
    "        # print('res:',''.join(sorted(res)))\n",
    "        return ''.join(sorted(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        #imatate\n",
    "        c = Counter(s)\n",
    "        cnt = [0]*10\n",
    "        cnt[0] = c['z']\n",
    "        cnt[2] = c['w']\n",
    "        cnt[4] = c['u']\n",
    "        cnt[6] = c['x']\n",
    "        cnt[8] = c['g']\n",
    "\n",
    "        cnt[3] = c['h']-cnt[8]\n",
    "        cnt[5] = c['f']-cnt[4]\n",
    "        cnt[7] = c['s']-cnt[6]\n",
    "\n",
    "        cnt[1] = c['o']-cnt[0]-cnt[2]-cnt[4]\n",
    "        cnt[9] = c['i']-cnt[5]-cnt[6]-cnt[8]\n",
    "\n",
    "        return ''.join(str(x)*cnt[x] for x in range(10))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''dic  = {}\n",
    "        for i in s:\n",
    "            if i in dic:\n",
    "                dic[i] +=1\n",
    "            else:\n",
    "                dic[i] =1\n",
    "        ans = [0]*10\n",
    "        ans[0] = dic['z']\n",
    "        ans[8] = dic['g'] \n",
    "\n",
    "\n",
    "        ans[6] = dic['x']\n",
    "        ans[2] = dic['w']\n",
    "        ans[4]=dic['u']\n",
    "        \n",
    "        for i in dic:\n",
    "            if i in 'zero':\n",
    "                dic[i]-=1\n",
    "            elif i in 'eight':\n",
    "                dic[i] -=1\n",
    "            elif i in 'six':\n",
    "                dic[i] -=1\n",
    "        ans[3] = dic['h']\n",
    "        for i in dic:\n",
    "            if i in 'thr':\n",
    "                dic[i] -=1\n",
    "            elif i =='e':\n",
    "                dic[i] -=2\n",
    "        ans[5]= dic['f']\n",
    "        ans[7]= dic['s']\n",
    "        ans[1] = dic['o']\n",
    "        res = []\n",
    "        for i in range(len(ans)):\n",
    "            res += [i]*ans[i]\n",
    "        return res'''\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        a = [s.count(x) for x in 'zowhufxsgi']\n",
    "        a[3] -= a[8]\n",
    "        a[5] -= a[4]\n",
    "        a[7] -= a[6]\n",
    "\n",
    "        a[1] -= a[0] + a[2] + a[4]\n",
    "        a[9] -= a[5] + a[6] + a[8]\n",
    "\n",
    "        return ''.join(str(x) * a[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        char_to_count = collections.Counter(s)\n",
    "        num_to_count = dict()\n",
    "        num_to_count[0] = char_to_count.get(\"z\", 0) # \"zero\"\n",
    "        num_to_count[2] = char_to_count.get(\"w\", 0)\n",
    "        num_to_count[4] = char_to_count.get(\"u\", 0)\n",
    "        num_to_count[6] = char_to_count.get(\"x\", 0)\n",
    "        num_to_count[8] = char_to_count.get(\"g\", 0)\n",
    "\n",
    "        num_to_count[3] = char_to_count.get(\"h\", 0) - num_to_count[8]\n",
    "        num_to_count[5] = char_to_count.get(\"f\", 0) - num_to_count[4]\n",
    "        num_to_count[7] = char_to_count.get(\"s\", 0) - num_to_count[6]\n",
    "\n",
    "        num_to_count[1] = char_to_count.get(\"o\", 0) - num_to_count[0] - num_to_count[2] - num_to_count[4]\n",
    "\n",
    "        num_to_count[9] = (char_to_count.get(\"n\", 0) - num_to_count[1] - num_to_count[7]) // 2 # 除以2是因为, 一个nine对应两个n\n",
    "\n",
    "        # 英文映射到阿拉伯\n",
    "        res = \"\"\n",
    "        for i in range(10):\n",
    "            res += str(i) * num_to_count[i]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "这个题目,有点意思.类似于密码解码. 因为规律性太强, 一时无法记住. 此处直接根据结论把代码完成.\n",
    "这题可以作为一个解密软件, 输入是乱序的英文数字, 然后解密\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        print(c)\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        # count the freq of char in s\n",
    "        freq = {} \n",
    "        for ch in s:\n",
    "            if ch not in freq:\n",
    "                freq[ch] = 0\n",
    "            freq[ch] += 1\n",
    "        # count[0] - count[9] store the times of each number\n",
    "        count = [0] * 10 \n",
    "        count[0] = freq.get('z', 0)\n",
    "        count[2] = freq.get('w', 0)\n",
    "        count[4] = freq.get('u', 0)\n",
    "        count[6] = freq.get('x', 0)\n",
    "        count[8] = freq.get('g', 0)\n",
    "\n",
    "        count[3] = freq.get('h', 0) - count[8]\n",
    "        count[5] = freq.get('f', 0) - count[4]\n",
    "        count[7] = freq.get('s', 0) - count[6]\n",
    "\n",
    "        count[1] = freq.get('o', 0) - count[0] - count[2] - count[4]\n",
    "        count[9] = freq.get('i', 0) - count[5] - count[6] - count[8]\n",
    "\n",
    "        ret = \"\"\n",
    "        for i, c in enumerate(count):\n",
    "            ret +=  str(i) * c\n",
    "        return ret\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        numList = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']\n",
    "        n = len(s)\n",
    "        cntMap = {}\n",
    "        for w in s:\n",
    "            cntMap[w] = cntMap.get(w, 0) + 1\n",
    "        ansList = []\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = cntMap.get(\"z\", 0)\n",
    "        cnt[2] = cntMap.get(\"w\", 0)\n",
    "        cnt[4] = cntMap.get(\"u\", 0)\n",
    "        cnt[6] = cntMap.get(\"x\", 0)\n",
    "        cnt[8] = cntMap.get(\"g\", 0)\n",
    "\n",
    "        cnt[3] = cntMap.get(\"h\", 0) - cnt[8]\n",
    "        cnt[5] = cntMap.get(\"f\", 0) - cnt[4]\n",
    "        cnt[7] = cntMap.get(\"s\", 0) - cnt[6]\n",
    "\n",
    "        cnt[1] = cntMap.get(\"o\", 0) - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = cntMap.get(\"i\", 0) - cnt[5] - cnt[6] - cnt[8]\n",
    "        return ''.join(str(x) * cnt[x] for x in range(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        n0 = s.count('z')\n",
    "        n2 = s.count('w')\n",
    "        n8 = s.count('g')\n",
    "        n6 = s.count('x')\n",
    "        n3 = s.count('t') - n2 - n8\n",
    "        n4 = s.count('r') - n3 - n0\n",
    "        n7 = s.count('s') - n6\n",
    "        n1 = s.count('o') - n4 - n2 - n0\n",
    "        n5 = s.count('v') - n7\n",
    "        n9 = s.count('i') - n8 - n6 - n5\n",
    "        \n",
    "        ns = (n0,n1,n2,n3,n4,n5,n6,n7,n8,n9)\n",
    "        \n",
    "        return \"\".join((str(i)*n for i, n in enumerate(ns)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        letterCount = {}\n",
    "        for c in s:\n",
    "            letterCount[c] = letterCount.get(c, 0) + 1\n",
    "\n",
    "        digitCount = [0] * 10\n",
    "\n",
    "        def minus(keyChar, subCount, digit):\n",
    "            count = letterCount.get(keyChar, 0)\n",
    "            if count == 0:\n",
    "                return\n",
    "            digitCount[digit] += count\n",
    "            for k, v in subCount.items():\n",
    "                letterCount[k] -= v * count\n",
    "\n",
    "        minus('w', {'t': 1, 'w': 1, 'o': 1}, 2)\n",
    "        minus('u', {'f': 1, 'o': 1, 'u': 1, 'r': 1}, 4)\n",
    "        minus('x', {'s': 1, 'i': 1, 'x': 1}, 6)\n",
    "        minus('z', {'z': 1, 'e': 1, 'r': 1, 'o': 1}, 0)\n",
    "        minus('f', {'f': 1, 'i': 1, 'v': 1, 'e': 1}, 5)\n",
    "        minus('o', {'o': 1, 'n': 1, 'e': 1}, 1)\n",
    "        minus('v', {'s': 1, 'e': 2, 'v': 1, 'n': 1}, 7)\n",
    "        minus('g', {'e': 1, 'i': 1, 'g': 1, 'h': 1, 't': 1}, 8)\n",
    "        minus('i', {'n': 2, 'i': 2, 'e': 1}, 9)\n",
    "        minus('r', {'t': 1, 'h': 2, 'r': 1, 'e': 2}, 3)\n",
    "\n",
    "        res = ''\n",
    "        for i in range(10):\n",
    "            if digitCount[i] > 0:\n",
    "                res += str(i) * digitCount[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num_str = \"\"\n",
    "        if \"u\" in s:\n",
    "            count = s.count(\"u\")\n",
    "            for ch in \"four\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '4'*count\n",
    "        if \"f\" in s:\n",
    "            count = s.count(\"f\")\n",
    "            for ch in \"five\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '5'*count\n",
    "        if \"x\" in s:\n",
    "            count = s.count(\"x\")\n",
    "            for ch in \"six\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '6'*count\n",
    "        if \"s\" in s:\n",
    "            count = s.count(\"s\")\n",
    "            for ch in \"seven\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '7'*count\n",
    "        if \"g\" in s:\n",
    "            count = s.count(\"g\")\n",
    "            for ch in \"eight\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '8'*count\n",
    "            count = 1\n",
    "        if \"n\" in s:\n",
    "            count = s.count(\"i\")\n",
    "            for ch in \"nine\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = num_str + '9'*count\n",
    "        if \"h\" in s:\n",
    "            count = s.count(\"h\") \n",
    "            for ch in \"three\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = '3'*count + num_str\n",
    "        if \"w\" in s:\n",
    "            count = s.count(\"w\")\n",
    "            for ch in \"two\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = '2'*count + num_str\n",
    "        if \"n\" in s:\n",
    "            count = s.count(\"n\")\n",
    "            for ch in \"one\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = '1'*count + num_str\n",
    "        if \"z\" in s:\n",
    "            count = s.count(\"z\")\n",
    "            for ch in \"zero\":\n",
    "                s = s.replace(ch,\"\",count)\n",
    "            num_str = '0'*count + num_str\n",
    "        return num_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        return \"0\" * cnt[\"z\"] + \\\n",
    "               \"1\" * (cnt[\"o\"] - cnt[\"z\"] - cnt[\"u\"] - cnt[\"w\"]) + \\\n",
    "               \"2\" * cnt[\"w\"] + \\\n",
    "               \"3\" * (cnt[\"r\"] - cnt[\"z\"] - cnt[\"u\"]) + \\\n",
    "               \"4\" * cnt[\"u\"] + \\\n",
    "               \"5\" * (cnt[\"v\"] - cnt[\"s\"] + cnt[\"x\"]) + \\\n",
    "               \"6\" * cnt[\"x\"] + \\\n",
    "               \"7\" * (cnt[\"s\"] - cnt[\"x\"]) + \\\n",
    "               \"8\" * (cnt[\"t\"] - cnt[\"w\"] - cnt[\"r\"] + cnt[\"z\"] + cnt[\"u\"]) + \\\n",
    "               \"9\" * ((cnt[\"n\"] - cnt[\"s\"] + cnt[\"x\"] - cnt[\"o\"] + cnt[\"z\"] + cnt[\"u\"] + cnt[\"w\"]) // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        '''\n",
    "        zero    z*          r\n",
    "        two     w*\n",
    "        six     x*  s\n",
    "        seven       s                   n\n",
    "        eight   g*      h\n",
    "        three           h   r\n",
    "        four                r   f\n",
    "        five                    f   i\n",
    "        nine                        i   nn\n",
    "        one                             n\n",
    "        '''\n",
    "        res = \"\"\n",
    "        hash = {}\n",
    "        for i in s:\n",
    "            if hash.get(i, None) == None:\n",
    "                hash[i] = 1\n",
    "            else:\n",
    "                hash[i] += 1\n",
    "        print(hash)\n",
    "        # 0\n",
    "        if hash.get('z', None) != None:\n",
    "            p = hash['z']\n",
    "            res += '0' * hash['z']\n",
    "            hash['z'] -= p\n",
    "            hash['r'] -= p\n",
    "        # 2\n",
    "        if hash.get('w', None) != None:\n",
    "            p = hash['w']\n",
    "            res += '2' * hash['w']\n",
    "            hash['w'] -= p\n",
    "        # 6\n",
    "        if hash.get('x', None) != None:\n",
    "            p = hash['x']\n",
    "            res += '6' * hash['x']\n",
    "            hash['x'] -= p\n",
    "            hash['s'] -= p\n",
    "            hash['i'] -= p\n",
    "        # 7\n",
    "        if hash.get('s', None) != None and hash.get('n', None) != None:\n",
    "            p = hash['s']\n",
    "            res += '7' * p\n",
    "            hash['s'] -= p\n",
    "            hash['n'] -= p\n",
    "        # 8\n",
    "        if hash.get('g', None) != None:\n",
    "            p = hash['g']\n",
    "            res += '8' * p\n",
    "            hash['g'] -= p\n",
    "            hash['h'] -= p\n",
    "            hash['i'] -= p\n",
    "        # 3\n",
    "        if hash.get('h', None) != None and hash.get('r', None) != None:\n",
    "            p = hash['h']\n",
    "            res += '3' * p\n",
    "            hash['h'] -= p\n",
    "            hash['r'] -= p\n",
    "        # 4\n",
    "        if hash.get('r', None) != None and hash.get('f', None) != None:\n",
    "            p = hash['r']\n",
    "            res += '4' * p\n",
    "            hash['r'] -= p\n",
    "            hash['f'] -= p\n",
    "        # 5\n",
    "        if hash.get('f', None) != None and hash.get('i', None) != None:\n",
    "            p = hash['f']\n",
    "            res += '5' * p\n",
    "            hash['f'] -= p\n",
    "            hash['i'] -= p\n",
    "        # 9\n",
    "        if hash.get('i', None) != None and hash.get('n', None) != None:\n",
    "            p = hash['i']\n",
    "            res += '9' * p\n",
    "            hash['i'] -= p\n",
    "            hash['n'] -= 2*p\n",
    "        # 1\n",
    "        if hash.get('n', None) != None:\n",
    "            p = hash['n']\n",
    "            res += '1' * p\n",
    "\n",
    "        return ''.join(sorted(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nums = [\"zero\", \"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\"]\n",
    "order = [(0, \"z\"), (2, \"w\"), (4, \"u\"), (5,\"f\"), (6,\"x\"),(7,\"s\"), (1,\"o\"),(8,\"g\"),(3,\"h\"), (9,\"i\")]\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        def reduce(num, v):\n",
    "            for c in nums[num]:\n",
    "                cnts[c] -= v\n",
    "\n",
    "        cnts = Counter(s)\n",
    "        ans = [0] * 10\n",
    "        for num, key in order:\n",
    "            v = cnts[key]\n",
    "            reduce(num, v)\n",
    "            ans[num] = v\n",
    "        return \"\".join(str(i) * v for i,v in enumerate(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        cnt=[0]*10\n",
    "        cnt[0]=c[\"z\"]\n",
    "        cnt[2]=c[\"w\"]\n",
    "        cnt[4]=c[\"u\"]\n",
    "        cnt[6]=c[\"x\"]\n",
    "        cnt[8]=c[\"g\"]\n",
    "        cnt[3]=c[\"h\"]-c[\"g\"]\n",
    "        cnt[5]=c[\"f\"]-c[\"u\"]\n",
    "        cnt[7]=c[\"s\"]-c[\"x\"]\n",
    "        cnt[1]=c[\"o\"]-c[\"z\"]-c[\"w\"]-c[\"u\"]\n",
    "        cnt[9]=c[\"i\"]-c[\"x\"]-c[\"g\"]-cnt[5]\n",
    "        s1=\"\"\n",
    "        for i in range(10):\n",
    "            s1+=str(i)*cnt[i]\n",
    "        return s1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nums = [\"zero\", \"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\"]\n",
    "order = [(0, \"z\"), (2, \"w\"), (4, \"u\"), (5,\"f\"), (6,\"x\"),(7,\"s\"), (1,\"o\"),(8,\"g\"),(3,\"h\"), (9,\"i\")]\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        def reduce(num, v):\n",
    "            for c in nums[num]:\n",
    "                cnts[c] -= v\n",
    "\n",
    "        cnts = Counter(s)\n",
    "        ans = [0] * 10\n",
    "        for num, key in order:\n",
    "            v = cnts[key]\n",
    "            reduce(num, v)\n",
    "            ans[num] = v\n",
    "        return \"\".join(str(i) * v for i,v in enumerate(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "num = [\"zero\", \"one\", 'two', \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\"]\n",
    "m = {a: str(i) for i, a in enumerate(num)}\n",
    "\n",
    "\n",
    "@cache\n",
    "def getC(s):\n",
    "    return Counter(s)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        res = []\n",
    "\n",
    "        def check(mid, n):\n",
    "            for k, v in n.items():\n",
    "                if c[k] < v * mid:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for n in  [\"six\",\"eight\", \"zero\", 'two',  \"four\",  \"one\", \"three\", \"five\",  \"seven\", \"nine\"]:\n",
    "            left = -1\n",
    "            right = len(s) + 1\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if check(mid, getC(n)):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "                \n",
    "            print(left, n)\n",
    "            for k, v in getC(n).items():\n",
    "                c[k] -= left * v\n",
    "            res += [m[n]] * left\n",
    "        res.sort()\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        print(c)\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        # count the freq of char in s\n",
    "        freq = {} \n",
    "        for ch in s:\n",
    "            if ch not in freq:\n",
    "                freq[ch] = 0\n",
    "            freq[ch] += 1\n",
    "        # count[0] - count[9] store the times of each number\n",
    "        count = [0] * 10 \n",
    "        count[0] = freq.get('z', 0)\n",
    "        count[2] = freq.get('w', 0)\n",
    "        count[4] = freq.get('u', 0)\n",
    "        count[6] = freq.get('x', 0)\n",
    "        count[8] = freq.get('g', 0)\n",
    "\n",
    "        count[3] = freq.get('h', 0) - count[8]\n",
    "        count[5] = freq.get('f', 0) - count[4]\n",
    "        count[7] = freq.get('s', 0) - count[6]\n",
    "\n",
    "        count[1] = freq.get('o', 0) - count[0] - count[2] - count[4]\n",
    "        count[9] = freq.get('i', 0) - count[5] - count[6] - count[8]\n",
    "\n",
    "        ret = \"\"\n",
    "        for i, c in enumerate(count):\n",
    "            ret +=  str(i) * c\n",
    "        return ret\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        cs = dict()\n",
    "        nums = list()\n",
    "        keys = [\"zero\",\"one\",\"two\",\"three\",\"four\",\"five\",\"six\",\"seven\",\"eight\",\"nine\"]\n",
    "        keys = [list(key) for key in keys]\n",
    "        for x in s: cs[x] = cs.get(x,0) + 1\n",
    "        if cs.get(\"z\",0)>0:\n",
    "            k = cs[\"z\"]\n",
    "            nums.extend([\"0\"]*k)\n",
    "            for c in \"zero\": cs[c] -= k\n",
    "        if cs.get(\"w\",0)>0:\n",
    "            k = cs[\"w\"]\n",
    "            nums.extend([\"2\"]*k)\n",
    "            for c in \"two\": cs[c] -= k        \n",
    "        if cs.get(\"x\",0)>0:\n",
    "            k = cs[\"x\"]\n",
    "            nums.extend([\"6\"]*k)\n",
    "            for c in \"six\": cs[c] -= k\n",
    "        if cs.get(\"u\",0)>0:\n",
    "            k = cs[\"u\"]\n",
    "            nums.extend([\"4\"]*k)\n",
    "            for c in \"four\": cs[c] -= k\n",
    "        if cs.get(\"f\",0)>0:\n",
    "            k = cs[\"f\"]\n",
    "            nums.extend([\"5\"]*k)\n",
    "            for c in \"five\": cs[c] -= k            \n",
    "        if cs.get(\"g\",0)>0:\n",
    "            k = cs[\"g\"]\n",
    "            nums.extend([\"8\"]*k)\n",
    "            for c in \"eight\": cs[c] -= k\n",
    "        if cs.get(\"h\",0)>0:\n",
    "            k = cs[\"h\"]\n",
    "            nums.extend([\"3\"]*k)\n",
    "            for c in \"three\": cs[c] -= k\n",
    "        if cs.get(\"o\",0)>0:\n",
    "            k = cs[\"o\"]\n",
    "            nums.extend([\"1\"]*k)\n",
    "            for c in \"one\": cs[c] -= k            \n",
    "        if cs.get(\"s\",0)>0:\n",
    "            k = cs[\"s\"]\n",
    "            nums.extend([\"7\"]*k)\n",
    "            for c in \"seven\": cs[c] -= k            \n",
    "        if cs.get(\"n\",0)>0:\n",
    "            k = cs[\"i\"]\n",
    "            nums.extend([\"9\"]*k)\n",
    "            for c in \"nine\": cs[c] -= k            \n",
    "        # print(cs)\n",
    "        nums = sorted(nums)\n",
    "        return \"\".join(nums)\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        arr, cnt = [0] * 10, Counter(s)\n",
    "        arr[0] = cnt['z']\n",
    "        arr[2] = cnt['w']\n",
    "        arr[6] = cnt['x']\n",
    "        arr[8] = cnt['g']\n",
    "        arr[3] = cnt['h'] - arr[8]\n",
    "        arr[4] = cnt['r'] - arr[3] - arr[0]\n",
    "        arr[1] = cnt['o'] - arr[0] - arr[2] - arr[4]\n",
    "        arr[5] = cnt['f'] - arr[4]\n",
    "        arr[7] = cnt['s'] - arr[6]\n",
    "        arr[9] = cnt['i'] - arr[5] - arr[6] - arr[8]    \n",
    "        ans = \"\"\n",
    "        for i, n in enumerate(arr):\n",
    "            ans += str(i) * n\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        letterCount = {}\n",
    "        for c in s:\n",
    "            letterCount[c] = letterCount.get(c, 0) + 1\n",
    "\n",
    "        digitCount = [0] * 10\n",
    "\n",
    "        def minus(keyChar, subCount, digit):\n",
    "            count = letterCount.get(keyChar, 0)\n",
    "            if count == 0:\n",
    "                return\n",
    "            digitCount[digit] += count\n",
    "            for k, v in subCount.items():\n",
    "                letterCount[k] -= v * count\n",
    "\n",
    "        minus('w', {'t': 1, 'w': 1, 'o': 1}, 2)\n",
    "        minus('u', {'f': 1, 'o': 1, 'u': 1, 'r': 1}, 4)\n",
    "        minus('x', {'s': 1, 'i': 1, 'x': 1}, 6)\n",
    "        minus('z', {'z': 1, 'e': 1, 'r': 1, 'o': 1}, 0)\n",
    "        minus('f', {'f': 1, 'i': 1, 'v': 1, 'e': 1}, 5)\n",
    "        minus('o', {'o': 1, 'n': 1, 'e': 1}, 1)\n",
    "        minus('v', {'s': 1, 'e': 2, 'v': 1, 'n': 1}, 7)\n",
    "        minus('g', {'e': 1, 'i': 1, 'g': 1, 'h': 1, 't': 1}, 8)\n",
    "        minus('i', {'n': 2, 'i': 2, 'e': 1}, 9)\n",
    "        minus('r', {'t': 1, 'h': 2, 'r': 1, 'e': 2}, 3)\n",
    "\n",
    "        res = ''\n",
    "        for i in range(10):\n",
    "            if digitCount[i] > 0:\n",
    "                res += str(i) * digitCount[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        counter=Counter(s)\n",
    "        digits=[0]*10\n",
    "        if 'z' in counter:\n",
    "            digits[0]=counter['z']\n",
    "            for c in 'zero':\n",
    "                counter[c]-=digits[0]\n",
    "        if 'w' in counter:\n",
    "            digits[2]=counter['w']\n",
    "            for c in 'two':\n",
    "                counter[c]-=digits[2]\n",
    "        if 'u' in counter:\n",
    "            digits[4]=counter['u']\n",
    "            for c in 'four':\n",
    "                counter[c]-=digits[4]    \n",
    "        if 'x' in counter:\n",
    "            digits[6]=counter['x']\n",
    "            for c in 'six':\n",
    "                counter[c]-=digits[6]  \n",
    "        if 'g' in counter:\n",
    "            digits[8]=counter['g']\n",
    "            for c in 'eight':\n",
    "                counter[c]-=digits[8]   \n",
    "        if 'o' in counter:\n",
    "            digits[1]=counter['o']\n",
    "            for c in 'one':\n",
    "                counter[c]-=digits[1]      \n",
    "        if 't' in counter:\n",
    "            digits[3]=counter['t']\n",
    "            for c in 'three':\n",
    "                counter[c]-=digits[3] \n",
    "        if 'f' in counter:\n",
    "            digits[5]=counter['f']\n",
    "            for c in 'five':\n",
    "                counter[c]-=digits[5] \n",
    "        if 's' in counter:\n",
    "            digits[7]=counter['s']\n",
    "            for c in 'seven':\n",
    "                counter[c]-=digits[7]    \n",
    "        if 'i' in counter:\n",
    "            digits[9]=counter['i']\n",
    "        result=''\n",
    "        for i in range(10):\n",
    "            result+=str(i)*digits[i]   \n",
    "        return result\n",
    "\n",
    "        '''\n",
    "        a=['one','three','five','seven','nine']\n",
    "        d_c={}\n",
    "        for i in range(5):\n",
    "            for c in a[i]:\n",
    "                if c not in d_c:\n",
    "                    d_c[c]=1\n",
    "                else:\n",
    "                    d_c[c]+=1\n",
    "        print(d_c)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        C = Counter(s)\n",
    "        zeros = C['z'] if 'z' in C else 0\n",
    "        if zeros:\n",
    "            C['z']-=zeros;C['e']-=zeros;C['r']-=zeros;C['o']-=zeros        \n",
    "        twos = C['w'] if 'w' in C else 0\n",
    "        if twos:\n",
    "            C['t']-=twos;C['w']-=twos;C['o']-=twos\n",
    "        \n",
    "        sixs = C['x'] if 'x' in C else 0\n",
    "        if sixs:\n",
    "            C['s']-=sixs;C['i']-=sixs;C['x']-=sixs    \n",
    "\n",
    "        eights = C['g'] if 'g' in C else 0\n",
    "        if eights:\n",
    "            C['e']-=eights;C['i']-=eights;C['g']-=eights;C['h']-=eights;C['t']-=eights\n",
    "\n",
    "        threes = C['h'] if 'h' in C else 0\n",
    "        if threes:\n",
    "            C['t']-=threes;C['h']-=threes;C['r']-=threes;C['e']-=threes;C['e']-=threes\n",
    "        \n",
    "        fours = C['r'] if 'r' in C else 0\n",
    "        if fours:\n",
    "            C['f']-=fours;C['o']-=fours;C['u']-=fours;C['r']-=fours\n",
    "\n",
    "        fives = C['f'] if 'f' in C else 0\n",
    "        if fives:\n",
    "            C['f']-=fives;C['i']-=fives;C['v']-=fives;C['e']-=fives\n",
    "        \n",
    "        ones = C['o'] if 'o' in C else 0\n",
    "        sevens = C['s'] if 's' in C else 0\n",
    "        nines = C['i'] if 'i' in C else 0\n",
    "\n",
    "        rts = '0'*zeros + '1'*ones + '2'*twos + '3'*threes + '4'*fours + '5'*fives + '6'*sixs + '7'*sevens + '8'*eights + '9'*nines\n",
    "        return rts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        dic=dict()\n",
    "        ans=list()\n",
    "        a=[0]*10\n",
    "        for i in s:\n",
    "            dic[i]=dic.get(i,0)+1\n",
    "        if dic.get(\"z\",0)!=0:\n",
    "            dic['e']-=dic['z']\n",
    "            dic['r']-=dic['z']\n",
    "            dic['o']-=dic['z']\n",
    "            a[0]=dic['z']\n",
    "            dic['z']=0\n",
    "        if dic.get(\"u\",0)!=0:\n",
    "            dic['f']-=dic['u']\n",
    "            dic['r']-=dic['u']\n",
    "            dic['o']-=dic['u']\n",
    "            a[4]=dic['u']\n",
    "            dic['u']=0\n",
    "        if dic.get(\"w\",0)!=0:\n",
    "            dic['t']-=dic['w']\n",
    "            dic['o']-=dic['w']\n",
    "            a[2]=dic['w']\n",
    "            dic['w']=0\n",
    "        if dic.get(\"g\",0)!=0:\n",
    "            dic['e']-=dic['g']\n",
    "            dic['i']-=dic['g']\n",
    "            dic['h']-=dic['g']\n",
    "            dic['t']-=dic['g']\n",
    "            a[8]=dic['g']\n",
    "            dic['g']=0\n",
    "        if dic.get(\"x\",0)!=0:\n",
    "            dic['s']-=dic['x']\n",
    "            dic['i']-=dic['x']\n",
    "            a[6]=dic['x']\n",
    "            dic['x']=0\n",
    "        if dic.get(\"o\",0)!=0:\n",
    "            dic['e']-=dic['o']\n",
    "            dic['n']-=dic['o']\n",
    "            a[1]=dic['o']\n",
    "            dic['o']=0\n",
    "        if dic.get(\"s\",0)!=0:\n",
    "            dic['e']-=2*dic['s']\n",
    "            dic['v']-=dic['s']\n",
    "            dic['n']-=dic['s']\n",
    "            a[7]=dic['s']\n",
    "            dic['s']=0\n",
    "        if dic.get(\"h\",0)!=0:\n",
    "            dic['e']-=2*dic['h']\n",
    "            dic['t']-=dic['h']\n",
    "            dic['r']-=dic['h']\n",
    "            a[3]=dic['h']\n",
    "            dic['h']=0\n",
    "        a[5]=dic.get(\"f\",0)\n",
    "        a[9]=dic.get(\"n\",0)//2\n",
    "        for i in range(10):\n",
    "            ans.extend([str(i)]*a[i])\n",
    "        return \"\".join(ans)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        counter = Counter(s)\n",
    "        nums_count = [0] * 10\n",
    "\n",
    "        def subtract(num_str, count):\n",
    "            for c in num_str:\n",
    "                counter[c] -= count\n",
    "\n",
    "        nums_count[0] = counter['z']\n",
    "        subtract('zero', nums_count[0])\n",
    "    \n",
    "        nums_count[6] = counter['x']\n",
    "        subtract('six', nums_count[6])\n",
    "\n",
    "        nums_count[8] = counter['g']\n",
    "        subtract('eight', nums_count[8])\n",
    "\n",
    "        nums_count[2] = counter['w']\n",
    "        subtract('two', nums_count[2])\n",
    "\n",
    "        nums_count[7] = counter['s']\n",
    "        subtract('seven', nums_count[7])\n",
    "\n",
    "        nums_count[5] = counter['v']\n",
    "        subtract('five', nums_count[5])\n",
    "\n",
    "        nums_count[4] = counter['f']\n",
    "        subtract('four', nums_count[4])\n",
    "\n",
    "        nums_count[3] = counter['h']\n",
    "        subtract('three', nums_count[3])\n",
    "\n",
    "        nums_count[9] = counter['i']\n",
    "        subtract('nine', nums_count[9])\n",
    "\n",
    "        nums_count[1] = counter['o']\n",
    "        subtract('one', nums_count[1])\n",
    "\n",
    "        res = ''\n",
    "\n",
    "        for idx in range(10):\n",
    "            res += f'{idx}' * nums_count[idx]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        n0, n2, n4, n6, n8 = cnt['z'], cnt['w'], cnt['u'], cnt['x'], cnt['g']\n",
    "        n1, n5, n7 = cnt['o'] - n0 - n2 - n4, cnt['f'] - n4, cnt['s'] - n6\n",
    "        n3, n9 = cnt['r'] - n0 - n4, cnt['i'] - n5 - n6 - n8\n",
    "        return '0'*n0 + '1'*n1 + '2'*n2 + '3'*n3 + '4'*n4 + '5'*n5 + '6'*n6 + '7'*n7 + '8'*n8 + '9'*n9\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        cs = dict()\n",
    "        ans = dict()\n",
    "        nums = list()\n",
    "        keys = [\"zero\",\"one\",\"two\",\"three\",\"four\",\"five\",\"six\",\"seven\",\"eight\",\"nine\"]\n",
    "        keys = [list(key) for key in keys]\n",
    "        for x in s: cs[x] = cs.get(x,0) + 1\n",
    "        if cs.get(\"z\",0)>0:\n",
    "            k = cs[\"z\"]\n",
    "            ans[\"0\"] = k\n",
    "            for c in \"zero\": cs[c] -= k\n",
    "        if cs.get(\"w\",0)>0:\n",
    "            k = cs[\"w\"]\n",
    "            ans[\"2\"] = k\n",
    "            for c in \"two\": cs[c] -= k        \n",
    "        if cs.get(\"x\",0)>0:\n",
    "            k = cs[\"x\"]\n",
    "            ans[\"6\"] = k\n",
    "            for c in \"six\": cs[c] -= k\n",
    "        if cs.get(\"u\",0)>0:\n",
    "            k = cs[\"u\"]\n",
    "            ans[\"4\"] = k\n",
    "            for c in \"four\": cs[c] -= k\n",
    "        if cs.get(\"f\",0)>0:\n",
    "            k = cs[\"f\"]\n",
    "            ans[\"5\"] = k\n",
    "            for c in \"five\": cs[c] -= k            \n",
    "        if cs.get(\"g\",0)>0:\n",
    "            k = cs[\"g\"]\n",
    "            ans[\"8\"]= k\n",
    "            for c in \"eight\": cs[c] -= k\n",
    "        if cs.get(\"h\",0)>0:\n",
    "            k = cs[\"h\"]\n",
    "            ans[\"3\"] = k\n",
    "            for c in \"three\": cs[c] -= k\n",
    "        if cs.get(\"o\",0)>0:\n",
    "            k = cs[\"o\"]\n",
    "            ans[\"1\"] = k\n",
    "            for c in \"one\": cs[c] -= k            \n",
    "        if cs.get(\"s\",0)>0:\n",
    "            k = cs[\"s\"]\n",
    "            ans[\"7\"] = k\n",
    "            for c in \"seven\": cs[c] -= k            \n",
    "        if cs.get(\"n\",0)>0:\n",
    "            k = cs[\"i\"]\n",
    "            ans[\"9\"] = k\n",
    "            for c in \"nine\": cs[c] -= k            \n",
    "        # print(cs)\n",
    "        for x in list(\"0123456789\"):\n",
    "            if x in ans: nums.extend([x]*ans[x])\n",
    "        # nums = sorted(nums)\n",
    "        return \"\".join(nums)\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        letterCount = {}\n",
    "        for c in s:\n",
    "            letterCount[c] = letterCount.get(c, 0) + 1\n",
    "\n",
    "        digitCount = [0] * 10\n",
    "\n",
    "        def minus(keyChar, subCount, digit):\n",
    "            count = letterCount.get(keyChar, 0)\n",
    "            if count == 0:\n",
    "                return\n",
    "            digitCount[digit] += count\n",
    "            for k, v in subCount.items():\n",
    "                letterCount[k] -= v * count\n",
    "\n",
    "        minus('w', {'t': 1, 'w': 1, 'o': 1}, 2)\n",
    "        minus('u', {'f': 1, 'o': 1, 'u': 1, 'r': 1}, 4)\n",
    "        minus('x', {'s': 1, 'i': 1, 'x': 1}, 6)\n",
    "        minus('z', {'z': 1, 'e': 1, 'r': 1, 'o': 1}, 0)\n",
    "        minus('f', {'f': 1, 'i': 1, 'v': 1, 'e': 1}, 5)\n",
    "        minus('o', {'o': 1, 'n': 1, 'e': 1}, 1)\n",
    "        minus('v', {'s': 1, 'e': 2, 'v': 1, 'n': 1}, 7)\n",
    "        minus('g', {'e': 1, 'i': 1, 'g': 1, 'h': 1, 't': 1}, 8)\n",
    "        minus('i', {'n': 2, 'i': 2, 'e': 1}, 9)\n",
    "        minus('r', {'t': 1, 'h': 2, 'r': 1, 'e': 2}, 3)\n",
    "\n",
    "        res = ''\n",
    "        for i in range(10):\n",
    "            if digitCount[i] > 0:\n",
    "                res += str(i) * digitCount[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num = [0,0,0,0,0,0,0,0,0,0]\n",
    "        s = list(s)\n",
    "        num[2] = s.count('w')\n",
    "        num[0] = s.count('z')\n",
    "        num[8] = s.count('g')\n",
    "        num[6] = s.count('x')\n",
    "        num[7] = s.count('s')-num[6]\n",
    "        num[3] = s.count('h')-num[8]\n",
    "        num[4] = s.count('r')-num[3]-num[0]\n",
    "        num[1] = s.count('o')-num[4]-num[0]-num[2]\n",
    "        num[5] = s.count('f')-num[4]\n",
    "        num[9] = (len(s)-sum(num)*3-num[5]-num[7]*2-num[4]-num[3]*2-num[8]*2-num[0])//4\n",
    "        result = ''\n",
    "        for i in range(10):\n",
    "            result += str(i)*num[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        maps = {}\n",
    "        for i in s:\n",
    "            if i in maps:\n",
    "                maps[i]+=1\n",
    "            else:\n",
    "                maps[i] = 1\n",
    "\n",
    "        ans = ''\n",
    "\n",
    "        lists = ['zero','six','four','eight','two','three','five','seven','nine','one']\n",
    "        nums =  [0,6,4,8,2,3,5,7,9,1]\n",
    "\n",
    "        index = 0\n",
    "\n",
    "        while index<len(lists):\n",
    "            needs = []\n",
    "            for i in lists[index]:\n",
    "                if i in maps:\n",
    "                    needs.append(maps[i])\n",
    "                else:\n",
    "                    needs = []\n",
    "                    break\n",
    "            if len(needs):\n",
    "                v = min(needs)\n",
    "                if v:\n",
    "                    for j in lists[index]:\n",
    "                        maps[j]-=v\n",
    "                ans += str(nums[index]) * v\n",
    "                #print(lists[index],v)\n",
    "            index+=1\n",
    "        ans = \"\".join(sorted(ans))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        ct = Counter(s)\n",
    "        \n",
    "        a0 = ct['z']\n",
    "        a2 = ct['w']\n",
    "        a6 = ct['x']\n",
    "        a8 = ct['g']\n",
    "        \n",
    "        a7 = ct['s'] - a6\n",
    "        a3 = ct['t'] - a2 - a8\n",
    "        a4 = ct['r'] - a3 - a0\n",
    "        a1 = ct['o'] - a4 - a2 - a0\n",
    "        a5 = ct['v'] - a7\n",
    "        a9 = ct['i'] - a8 - a6 - a5\n",
    "\n",
    "        return \"0\"*a0 + \"1\"*a1 + \"2\"*a2 + \"3\"*a3 + \"4\"*a4 + \"5\"*a5 + \"6\"*a6 + \"7\"*a7 + \"8\" * a8 + \"9\" * a9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# zero   z具有唯一性\n",
    "# two    w具有唯一性\n",
    "# eight->three->four->five  g具有唯一性 -> h具有唯一性 -> r具有唯一性 -> f具有唯一性\n",
    "# six->seven->nine    x具有唯一性 -> s具有唯一性 -> i具有唯一性\n",
    "# one    # 最后\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        answer_list = list()\n",
    "        one_to_nine_frequency_list = [0] * 10 \n",
    "        s_frequency_list = [0] * 26 \n",
    "        for letter in s:\n",
    "            s_frequency_list[ord(letter) - ord('a')] += 1\n",
    "        rule(s_frequency_list, one_to_nine_frequency_list)\n",
    "        for index in range(10):\n",
    "            answer_list.append(one_to_nine_frequency_list[index] * str(index))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def rule(s_frequency_list, one_to_nine_frequency_list):\n",
    "    zero_count = s_frequency_list[25]\n",
    "    one_to_nine_frequency_list[0] += zero_count\n",
    "    s_frequency_list[25] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= zero_count\n",
    "\n",
    "    two_count = s_frequency_list[22]\n",
    "    one_to_nine_frequency_list[2] += two_count\n",
    "    s_frequency_list[22] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= two_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= two_count\n",
    "\n",
    "    eight_count = s_frequency_list[6]\n",
    "    one_to_nine_frequency_list[8] += eight_count\n",
    "    s_frequency_list[6] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('h') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('t') - ord('a')] -= eight_count\n",
    "\n",
    "    three_count = s_frequency_list[7]\n",
    "    one_to_nine_frequency_list[3] += three_count\n",
    "    s_frequency_list[7] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "\n",
    "    four_count = s_frequency_list[17]\n",
    "    one_to_nine_frequency_list[4] += four_count\n",
    "    s_frequency_list[17] = 0 \n",
    "    s_frequency_list[ord('f') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('u') - ord('a')] -= four_count\n",
    "     \n",
    "    five_count = s_frequency_list[5]\n",
    "    one_to_nine_frequency_list[5] += five_count\n",
    "    s_frequency_list[5] = 0 \n",
    "    s_frequency_list[ord('i') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= five_count\n",
    "\n",
    "    six_count = s_frequency_list[23]\n",
    "    one_to_nine_frequency_list[6] += six_count\n",
    "    s_frequency_list[23] = 0 \n",
    "    s_frequency_list[ord('s') - ord('a')] -= six_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= six_count\n",
    "\n",
    "    seven_count = s_frequency_list[18]\n",
    "    one_to_nine_frequency_list[7] += seven_count\n",
    "    s_frequency_list[18] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= seven_count\n",
    "\n",
    "    nine_count = s_frequency_list[8]\n",
    "    one_to_nine_frequency_list[9] += nine_count\n",
    "    s_frequency_list[8] = 0 \n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= nine_count\n",
    "    \n",
    "    one_count = s_frequency_list[4]\n",
    "    one_to_nine_frequency_list[1] += one_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        s1=[]\n",
    "        while 'z' in s:\n",
    "            s=s.replace('z','',1)\n",
    "            s=s.replace('e', '', 1)\n",
    "            s=s.replace('r', '', 1)\n",
    "            s=s.replace('o', '', 1)\n",
    "            s1=s1+['0']\n",
    "        while 'g' in s:\n",
    "            s=s.replace('e','',1)\n",
    "            s=s.replace('i', '', 1)\n",
    "            s=s.replace('g', '', 1)\n",
    "            s=s.replace('h', '', 1)\n",
    "            s=s.replace('t', '', 1)\n",
    "            s1=s1+['8']\n",
    "        while 'u' in s:\n",
    "            s=s.replace('f','',1)\n",
    "            s=s.replace('o', '', 1)\n",
    "            s=s.replace('u', '', 1)\n",
    "            s=s.replace('r', '', 1)\n",
    "            s1=s1+['4']\n",
    "        while 'w' in s:\n",
    "            s=s.replace('t','',1)\n",
    "            s=s.replace('w', '', 1)\n",
    "            s=s.replace('o', '', 1)\n",
    "            s1=s1+['2']\n",
    "\n",
    "        while 'x' in s:\n",
    "            s=s.replace('s','',1)\n",
    "            s=s.replace('i', '', 1)\n",
    "            s=s.replace('x', '', 1)\n",
    "            s1=s1+['6']\n",
    "        while 'f' in s:\n",
    "            s=s.replace('f','',1)\n",
    "            s=s.replace('i', '', 1)\n",
    "            s=s.replace('v', '', 1)\n",
    "            s=s.replace('e', '', 1)\n",
    "            s1=s1+['5']\n",
    "        while 'v' in s:\n",
    "            s=s.replace('s','',1)\n",
    "            s=s.replace('e', '', 2)\n",
    "            s=s.replace('v', '', 1)\n",
    "            s=s.replace('n', '', 1)\n",
    "            s1=s1+['7']\n",
    "        while 't' in s:\n",
    "            s=s.replace('t','',1)\n",
    "            s=s.replace('h', '', 1)\n",
    "            s=s.replace('r', '', 1)\n",
    "            s=s.replace('e', '', 2)\n",
    "            s1=s1+['3']\n",
    "        while 'o' in s:\n",
    "            s=s.replace('o','',1)\n",
    "            s1=s1+['1']\n",
    "        while 'i' in s:\n",
    "            s=s.replace('i','',1)\n",
    "            s1=s1+['9']\n",
    "        s1.sort()\n",
    "        return ''.join(s1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        letterCnt = dict(collections.Counter(s))\n",
    "        numberCnt = {}\n",
    "        seq = [('z', 'ro', '0'), ('x', 'i', '6'), ('w', 'o', '2'), ('g', 'i', '8'), ('u', 'for', '4'), ('r', '', '3'), ('f', 'iv', '5'), ('v', '', '7'), ('o', '', '1'), ('i', '', '9')]\n",
    "\n",
    "        for it in seq:\n",
    "            if letterCnt.get(it[0]):\n",
    "                print(it[0])\n",
    "                numberCnt[it[2]] = letterCnt[it[0]]\n",
    "                for ch in it[1]:\n",
    "                    letterCnt[ch] -= letterCnt[it[0]]\n",
    "                \n",
    "                print(letterCnt)\n",
    "\n",
    "        print(numberCnt)\n",
    "\n",
    "        return \"\".join([k * v for k, v in sorted(numberCnt.items(), key=lambda item: item[0])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        answer_list = list()\n",
    "        one_to_nine_frequency_list = [0] * 10 \n",
    "        s_frequency_list = [0] * 26 \n",
    "        for letter in s:\n",
    "            s_frequency_list[ord(letter) - ord('a')] += 1\n",
    "        rule(s_frequency_list, one_to_nine_frequency_list)\n",
    "        for index in range(10):\n",
    "            answer_list.append(one_to_nine_frequency_list[index] * str(index))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def rule(s_frequency_list, one_to_nine_frequency_list):\n",
    "    zero_count = s_frequency_list[25]\n",
    "    one_to_nine_frequency_list[0] += zero_count\n",
    "    s_frequency_list[25] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= zero_count\n",
    "\n",
    "    two_count = s_frequency_list[22]\n",
    "    one_to_nine_frequency_list[2] += two_count\n",
    "    s_frequency_list[22] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= two_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= two_count\n",
    "\n",
    "    eight_count = s_frequency_list[6]\n",
    "    one_to_nine_frequency_list[8] += eight_count\n",
    "    s_frequency_list[6] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('h') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('t') - ord('a')] -= eight_count\n",
    "\n",
    "    three_count = s_frequency_list[7]\n",
    "    one_to_nine_frequency_list[3] += three_count\n",
    "    s_frequency_list[7] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "\n",
    "    four_count = s_frequency_list[17]\n",
    "    one_to_nine_frequency_list[4] += four_count\n",
    "    s_frequency_list[17] = 0 \n",
    "    s_frequency_list[ord('f') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('u') - ord('a')] -= four_count\n",
    "     \n",
    "    five_count = s_frequency_list[5]\n",
    "    one_to_nine_frequency_list[5] += five_count\n",
    "    s_frequency_list[5] = 0 \n",
    "    s_frequency_list[ord('i') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= five_count\n",
    "\n",
    "    six_count = s_frequency_list[23]\n",
    "    one_to_nine_frequency_list[6] += six_count\n",
    "    s_frequency_list[23] = 0 \n",
    "    s_frequency_list[ord('s') - ord('a')] -= six_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= six_count\n",
    "\n",
    "    seven_count = s_frequency_list[18]\n",
    "    one_to_nine_frequency_list[7] += seven_count\n",
    "    s_frequency_list[18] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= seven_count\n",
    "\n",
    "    nine_count = s_frequency_list[8]\n",
    "    one_to_nine_frequency_list[9] += nine_count\n",
    "    s_frequency_list[8] = 0 \n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= nine_count\n",
    "    \n",
    "    one_count = s_frequency_list[4]\n",
    "    one_to_nine_frequency_list[1] += one_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        cnt[0] = c[\"z\"]\n",
    "        cnt[2] = c[\"w\"]\n",
    "        cnt[4] = c[\"u\"]\n",
    "        cnt[6] = c[\"x\"]\n",
    "        cnt[8] = c[\"g\"]\n",
    "\n",
    "        cnt[3] = c[\"h\"] - cnt[8]\n",
    "        cnt[5] = c[\"f\"] - cnt[4]\n",
    "        cnt[7] = c[\"s\"] - cnt[6]\n",
    "        \n",
    "        cnt[1] = c[\"o\"] - cnt[0] - cnt[2] - cnt[4]\n",
    "\n",
    "        cnt[9] = c[\"i\"] - cnt[5] - cnt[6] - cnt[8]\n",
    "\n",
    "        return \"\".join(str(x) * cnt[x] for x in range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c=Counter(s)\n",
    "        count=[0]*10\n",
    "        count[0]=c[\"z\"]\n",
    "        count[2]=c[\"w\"]\n",
    "        count[4]=c[\"u\"]\n",
    "        count[6]=c[\"x\"]\n",
    "        count[8]=c[\"g\"]\n",
    "        count[3]=c[\"h\"]-count[8]\n",
    "        count[5]=c[\"f\"]-count[4]\n",
    "        count[7]=c[\"s\"]-count[6]\n",
    "        count[1]=c[\"o\"]-count[0]-count[2]-count[4]\n",
    "        count[9]=c[\"i\"]-count[5]-count[6]-count[8]\n",
    "        return \"\".join(str(num)*count[num] for num in range(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/reconstruct-original-digits-from-english/\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # 摘抄自：https://leetcode.cn/problems/reconstruct-original-digits-from-english/discussion/comments/113209\n",
    "    # 思路：每个字母都有各自的特征字母，优先使用排序靠前的，如果用完了，则当前数字忽略，否则使用；\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        n0 = s.count('z')\n",
    "        n2 = s.count('w')\n",
    "        n8 = s.count('g')\n",
    "        n6 = s.count('x')\n",
    "        n3 = s.count('t') - n2 - n8\n",
    "        n4 = s.count('r') - n3 - n0\n",
    "        n7 = s.count('s') - n6\n",
    "        n1 = s.count('o') - n4 - n2 - n0\n",
    "        n5 = s.count('v') - n7\n",
    "        n9 = s.count('i') - n8 - n6 - n5\n",
    "\n",
    "        ns = (n0, n1, n2, n3, n4, n5, n6, n7, n8, n9)\n",
    "\n",
    "        return \"\".join((str(i) * n for i, n in enumerate(ns)))\n",
    "\n",
    "    def originalDigits_mine(self, s: str) -> str:\n",
    "        nums = [\n",
    "            \"zero\", \"one\", \"two\", \"three\", \"four\", \"five\",\n",
    "            \"six\", \"seven\", \"eight\", \"nine\"\n",
    "        ]\n",
    "        m = {\n",
    "            \"zero\": \"0\", \"three\": \"3\", \"six\": \"6\",\n",
    "            \"one\": \"1\",  \"four\": \"4\",  \"seven\": \"7\",\n",
    "            \"two\": \"2\",  \"five\": \"5\",  \"eight\": \"8\", \"nine\": \"9\",\n",
    "        }\n",
    "        total = len(s)\n",
    "        map = {}\n",
    "        for c in s:\n",
    "            if c not in map.keys():\n",
    "                map[c] = 1\n",
    "            else:\n",
    "                map[c] += 1\n",
    "        ans = \"\"\n",
    "        while total > 0:\n",
    "            for num in nums:\n",
    "                full = True\n",
    "                for c in num:\n",
    "                    if map.get(c, 0) <= 0:\n",
    "                        full = False\n",
    "                if full:\n",
    "                    ans += m[num]\n",
    "                    for c in num:\n",
    "                        map[c] -= 1\n",
    "                    total -= num.__len__()\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        counter=Counter(s)\n",
    "        digits=[0]*10\n",
    "        if 'z' in counter:\n",
    "            digits[0]=counter['z']\n",
    "            for c in 'zero':\n",
    "                counter[c]-=digits[0]\n",
    "        if 'w' in counter:\n",
    "            digits[2]=counter['w']\n",
    "            for c in 'two':\n",
    "                counter[c]-=digits[2]\n",
    "        if 'u' in counter:\n",
    "            digits[4]=counter['u']\n",
    "            for c in 'four':\n",
    "                counter[c]-=digits[4]    \n",
    "        if 'x' in counter:\n",
    "            digits[6]=counter['x']\n",
    "            for c in 'six':\n",
    "                counter[c]-=digits[6]  \n",
    "        if 'g' in counter:\n",
    "            digits[8]=counter['g']\n",
    "            for c in 'eight':\n",
    "                counter[c]-=digits[8]   \n",
    "        if 'o' in counter:\n",
    "            digits[1]=counter['o']\n",
    "            for c in 'one':\n",
    "                counter[c]-=digits[1]      \n",
    "        if 't' in counter:\n",
    "            digits[3]=counter['t']\n",
    "            for c in 'three':\n",
    "                counter[c]-=digits[3] \n",
    "        if 'f' in counter:\n",
    "            digits[5]=counter['f']\n",
    "            for c in 'five':\n",
    "                counter[c]-=digits[5] \n",
    "        if 's' in counter:\n",
    "            digits[7]=counter['s']\n",
    "            for c in 'seven':\n",
    "                counter[c]-=digits[7]    \n",
    "        if 'i' in counter:\n",
    "            digits[9]=counter['i']\n",
    "        result=''\n",
    "        for i in range(10):\n",
    "            result+=str(i)*digits[i]   \n",
    "        return result\n",
    "\n",
    "        '''\n",
    "        a=['one','three','five','seven','nine']\n",
    "        d_c={}\n",
    "        for i in range(5):\n",
    "            for c in a[i]:\n",
    "                if c not in d_c:\n",
    "                    d_c[c]=1\n",
    "                else:\n",
    "                    d_c[c]+=1\n",
    "        print(d_c)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIGITS = [\n",
    "    [0,'z',[]],\n",
    "    [2,'w',[]],\n",
    "    [4,'u',[]],\n",
    "    [6,'x',[]],\n",
    "    [8,'g',[]],\n",
    "    [5,'f',[4]],\n",
    "    [7,'s',[6]],\n",
    "    [3,'h',[8]],\n",
    "    [9,'i',[6,8,5]],\n",
    "    [1,'o',[0,2,4]]\n",
    "]\n",
    "class Solution:\n",
    "    def originalDigits(self, S: str) -> str:\n",
    "        fmap, ans, n = [0] * 26, [0] * 10, len(S)\n",
    "        for i in range(10):\n",
    "            dig, char, rems = DIGITS[i]\n",
    "            count = S.count(char)\n",
    "            for rem in rems: count -= ans[rem]\n",
    "            ans[dig] += count\n",
    "        return \"\".join([str(i) * ans[i] for i in range(10)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "      s = Counter(s)\n",
    "      freq = [0] * 10\n",
    "      freq[0] = 0 if \"z\" not in s else s[\"z\"]\n",
    "      freq[2] = 0 if \"w\" not in s else s[\"w\"]\n",
    "      freq[4] = 0 if \"u\" not in s else s[\"u\"]\n",
    "      freq[6] = 0 if \"x\" not in s else s[\"x\"]\n",
    "      freq[8] = 0 if \"g\" not in s else s[\"g\"]\n",
    "      freq[3] = 0 if \"h\" not in s else s[\"h\"] - freq[8]\n",
    "      freq[5] = 0 if \"f\" not in s else s[\"f\"] - freq[4]\n",
    "      freq[7] = 0 if \"v\" not in s else s[\"v\"] - freq[5]\n",
    "      freq[1] = 0 if \"o\" not in s else s[\"o\"] - freq[0] - freq[2] - freq[4]\n",
    "      freq[9] = 0 if \"i\" not in s else s[\"i\"] - freq[5] - freq[6] - freq[8]\n",
    "\n",
    "      return \"\".join(str(k) * v for k, v in enumerate(freq))\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        d = {}\n",
    "        for i in s:\n",
    "            if i not in d:\n",
    "                d[i] = 0\n",
    "            d[i]+=1\n",
    "        s = {}\n",
    "        if \"z\" in d:\n",
    "            s[0] = d['z']\n",
    "            d['e'] -= d['z']\n",
    "            d['r'] -= d['z']\n",
    "            d['o'] -= d['z']\n",
    "            d['z'] = 0\n",
    "        if \"x\" in d:\n",
    "            s[6] = d['x']\n",
    "            d['s'] -= d['x']\n",
    "            d['i'] -= d['x']\n",
    "            d['x'] = 0\n",
    "        if \"s\" in d and d['s'] > 0:\n",
    "            s[7] = d['s']\n",
    "            d['e'] -= 2*d['s']\n",
    "            d['v'] -= d['s']\n",
    "            d['n'] -= d['s']\n",
    "            d['s'] = 0\n",
    "        if \"v\" in d and d['v']>0:\n",
    "            s[5] = d['v']\n",
    "            d['f'] -= d['v']\n",
    "            d['i'] -= d['v']\n",
    "            d['e'] -= d['v']\n",
    "            d['v'] = 0\n",
    "        if 'f' in d and d['f'] > 0:\n",
    "            s[4] = d['f']\n",
    "            d['o'] -= d['f']\n",
    "            d['u'] -= d['f']\n",
    "            d['r'] -= d['f']\n",
    "            d['f'] = 0\n",
    "        if \"w\" in d:\n",
    "            s[2] = d['w']\n",
    "            d['t'] -= d['w']\n",
    "            d['o'] -= d['w']\n",
    "            d['w'] = 0\n",
    "        if \"o\" in d and d['o'] > 0:\n",
    "            s[1] = d['o']\n",
    "            d['n'] -= d['o']\n",
    "            d['e'] -= d['o']\n",
    "            d['o'] = 0\n",
    "        if \"r\" in d and d['r'] > 0:\n",
    "            s[3] = d['r']\n",
    "            d['t'] -= d['r']\n",
    "            d['h'] -= d['r']\n",
    "            d['e'] -= 2*d['r']\n",
    "            d['r'] = 0\n",
    "        print(d)\n",
    "        if \"n\" in d and d['n'] > 0:\n",
    "            s[9] = d['n']//2\n",
    "            d['i'] -= s[9]\n",
    "            d['e'] -= s[9]\n",
    "        if 'e' in d and d['e'] > 0:\n",
    "            s[8] = d['e']\n",
    "        x = \"\"\n",
    "        for i in sorted(s.items(),key=lambda x:x[0]):\n",
    "            x+=str(i[0])*i[1]\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        def get(key: str) -> int:\n",
    "            if key in map:\n",
    "                return map[key]\n",
    "            return 0\n",
    "        map = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] in map:\n",
    "                map[s[i]] += 1\n",
    "            else:\n",
    "                map[s[i]] = 1\n",
    "        record = {}\n",
    "        record = [0] * 10\n",
    "        record[6] = get('x')\n",
    "        record[7] = get('s') - record[6]\n",
    "        record[2] = get('w')\n",
    "        record[8] = get('g')\n",
    "        record[3] = get('t') - record[8] - record[2]\n",
    "        record[4] = get('u')\n",
    "        record[0] = get('z')\n",
    "        record[5] = get('v') - record[7]\n",
    "        record[1] = get('o') - record[0] - record[2] - record[4]\n",
    "        record[9] = get('i') - record[5] - record[6] - record[8]\n",
    "        res = ''\n",
    "        for i in range(10):\n",
    "            res += (str(i) * record[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        h = collections.defaultdict(int)\n",
    "        for v in s:\n",
    "            h[v]+=1\n",
    "        words = {\"zero\": \"0\", \n",
    "                 \"two\": \"2\", \n",
    "                 \"six\": \"6\", \n",
    "                 \"eight\": \"8\", \n",
    "                 \"four\": \"4\", \n",
    "                 \"one\": \"1\", \n",
    "                 \"three\": \"3\", \n",
    "                 \"five\": \"5\", \n",
    "                 \"seven\": \"7\", \n",
    "                 \"nine\": \"9\"}\n",
    "        ans = []\n",
    "        for word, num in words.items():\n",
    "            length = min([h[k] for k in word])\n",
    "            while length:\n",
    "                length -= 1\n",
    "                ans.append(num)\n",
    "                for k in word:\n",
    "                    h[k] -= 1\n",
    "        ans.sort()\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        answer_list = list()\n",
    "        one_to_nine_frequency_list = [0] * 10 \n",
    "        s_frequency_list = [0] * 26 \n",
    "        for letter in s:\n",
    "            s_frequency_list[ord(letter) - ord('a')] += 1\n",
    "        rule(s_frequency_list, one_to_nine_frequency_list)\n",
    "        for index in range(10):\n",
    "            answer_list.append(one_to_nine_frequency_list[index] * str(index))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def rule(s_frequency_list, one_to_nine_frequency_list):\n",
    "    zero_count = s_frequency_list[25]\n",
    "    one_to_nine_frequency_list[0] += zero_count\n",
    "    s_frequency_list[25] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= zero_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= zero_count\n",
    "\n",
    "    two_count = s_frequency_list[22]\n",
    "    one_to_nine_frequency_list[2] += two_count\n",
    "    s_frequency_list[22] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= two_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= two_count\n",
    "\n",
    "    eight_count = s_frequency_list[6]\n",
    "    one_to_nine_frequency_list[8] += eight_count\n",
    "    s_frequency_list[6] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('h') - ord('a')] -= eight_count\n",
    "    s_frequency_list[ord('t') - ord('a')] -= eight_count\n",
    "\n",
    "    three_count = s_frequency_list[7]\n",
    "    one_to_nine_frequency_list[3] += three_count\n",
    "    s_frequency_list[7] = 0 \n",
    "    s_frequency_list[ord('t') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('r') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= three_count\n",
    "\n",
    "    four_count = s_frequency_list[17]\n",
    "    one_to_nine_frequency_list[4] += four_count\n",
    "    s_frequency_list[17] = 0 \n",
    "    s_frequency_list[ord('f') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('o') - ord('a')] -= four_count\n",
    "    s_frequency_list[ord('u') - ord('a')] -= four_count\n",
    "     \n",
    "    five_count = s_frequency_list[5]\n",
    "    one_to_nine_frequency_list[5] += five_count\n",
    "    s_frequency_list[5] = 0 \n",
    "    s_frequency_list[ord('i') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= five_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= five_count\n",
    "\n",
    "    six_count = s_frequency_list[23]\n",
    "    one_to_nine_frequency_list[6] += six_count\n",
    "    s_frequency_list[23] = 0 \n",
    "    s_frequency_list[ord('s') - ord('a')] -= six_count\n",
    "    s_frequency_list[ord('i') - ord('a')] -= six_count\n",
    "\n",
    "    seven_count = s_frequency_list[18]\n",
    "    one_to_nine_frequency_list[7] += seven_count\n",
    "    s_frequency_list[18] = 0 \n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('v') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= seven_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= seven_count\n",
    "\n",
    "    nine_count = s_frequency_list[8]\n",
    "    one_to_nine_frequency_list[9] += nine_count\n",
    "    s_frequency_list[8] = 0 \n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('n') - ord('a')] -= nine_count\n",
    "    s_frequency_list[ord('e') - ord('a')] -= nine_count\n",
    "    \n",
    "    one_count = s_frequency_list[4]\n",
    "    one_to_nine_frequency_list[1] += one_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        sample = [\"zero\", \"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\"]\n",
    "        mid = {}\n",
    "        for item in s:\n",
    "            if item not in mid:\n",
    "                mid[item] = 1\n",
    "            else:\n",
    "                mid[item] += 1\n",
    "            \n",
    "        final = \"\"\n",
    "        w_count,t_count,u_count,o_count,x_count,s_count,v_count,g_count,n_count = 0,0,0,0,0,0,0,0,0\n",
    "        if 'z' in mid:##zero\n",
    "            final += '0' * mid['z']\n",
    "            mid['e'] -= mid['z']\n",
    "            mid['r'] -= mid['z']\n",
    "            mid['o'] -= mid['z']\n",
    "        if 'w' in mid:###two\n",
    "            w_count = mid['w']\n",
    "            mid['t'] -= mid['w']\n",
    "            mid['o'] -= mid['w']\n",
    "        if 'g' in mid:###eight\n",
    "            g_count = mid['g']\n",
    "            mid['e'] -= mid['g']\n",
    "            mid['i'] -= mid['g']\n",
    "            mid['h'] -= mid['g']\n",
    "            mid['t'] -= mid['g']\n",
    "        if 't' in mid and mid['t'] != 0:##three\n",
    "            t_count = mid['t']\n",
    "            mid['h'] -= mid['t']\n",
    "            mid['r'] -= mid['t']\n",
    "            mid['e'] -= 2*mid['t']\n",
    "        if 'u' in mid:###four\n",
    "            u_count = mid['u']\n",
    "            mid['f'] -= mid['u']\n",
    "            mid['o'] -= mid['u']\n",
    "            mid['r'] -= mid['u']\n",
    "        if 'o' in mid and mid['o'] != 0:###one\n",
    "            o_count = mid['o']\n",
    "            mid['n'] -= mid['o']\n",
    "            mid['e'] -= mid['o']\n",
    "        if 'x' in mid:####six\n",
    "            x_count = mid['x']\n",
    "            mid['s'] -= mid['x']\n",
    "            mid['i'] -= mid['x']\n",
    "        if 's' in mid and mid['s'] != 0:###seven\n",
    "            s_count = mid['s']\n",
    "            mid['e'] -= 2* mid['s']\n",
    "            mid['v'] -= mid['s']\n",
    "            mid['n'] -= mid['s']\n",
    "        if 'v' in mid and mid['v'] != 0:###five\n",
    "            v_count = mid['v']\n",
    "            mid['f'] -= mid['v']\n",
    "            mid['i'] -= mid['v']\n",
    "            mid['e'] -= mid['v']\n",
    "        if 'n' in mid and mid['n'] != 0:###nine\n",
    "            n_count = mid['n'] // 2\n",
    "        \n",
    "        final += '1' * o_count\n",
    "        final += '2' * w_count\n",
    "        final += '3' * t_count\n",
    "        final += '4' * u_count\n",
    "        final += '5' * v_count\n",
    "        final += '6' * x_count\n",
    "        final += '7' * s_count\n",
    "        final += '8' * g_count\n",
    "        final += '9' * n_count\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import Counter\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        nums = [\"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\", \"zero\"]\n",
    "        letter_dict = Counter(list(s))\n",
    "        num_dict = dict()\n",
    "        num_dict[0] = letter_dict.get(\"z\", 0)\n",
    "        num_dict[6] = letter_dict.get(\"x\", 0)\n",
    "        num_dict[8] = letter_dict.get(\"g\", 0)\n",
    "        num_dict[2] = letter_dict.get(\"w\", 0)\n",
    "        num_dict[4] = letter_dict.get(\"u\", 0)\n",
    "        num_dict[7] = letter_dict.get(\"s\", 0)-num_dict[6]\n",
    "        num_dict[5] = letter_dict.get(\"f\", 0)-num_dict[4]\n",
    "        num_dict[9] = letter_dict.get(\"i\", 0)-num_dict[8]-num_dict[6]-num_dict[5]\n",
    "        num_dict[1] = letter_dict.get(\"o\", 0)-num_dict[2]-num_dict[4]-num_dict[0]\n",
    "        num_dict[3] = letter_dict.get(\"h\", 0)-num_dict[8]\n",
    "        res=\"\"\n",
    "        for i in range(10):\n",
    "            if num_dict[i] != 0:\n",
    "                res += str(i)*num_dict[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        c=len(s)\n",
    "        ret=''\n",
    "        xx={}\n",
    "        ff=['zero','one','two','three','four','five','six','seven','eight','nine']\n",
    "        \n",
    "        zz=[['z',0],['w',2],['x',6],['g',8],['u',4],['t',3],['r',4],['f',5],['v',7],['o',1],['i',9]]\n",
    "        \n",
    "\n",
    "        for i in range(c):\n",
    "            if s[i] in xx:\n",
    "                xx[s[i]]+=1\n",
    "            else:\n",
    "                xx[s[i]]=1\n",
    "        #print(xx)\n",
    "        for i in range(11):\n",
    "            bz=zz[i][0]\n",
    "            sz=zz[i][1]\n",
    "            print(i,bz,sz)\n",
    "            while bz in xx and xx[bz]>0:\n",
    "                #print('in')\n",
    "                ret+=str(sz)\n",
    "                for j in ff[sz]:\n",
    "                    #print('-1',j)\n",
    "                    xx[j]-=1\n",
    "        ret=list(ret)\n",
    "        ret.sort()\n",
    "        ret=''.join(ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num = [0,0,0,0,0,0,0,0,0,0]\n",
    "        s = list(s)\n",
    "        num[2] = s.count('w')\n",
    "        num[0] = s.count('z')\n",
    "        num[8] = s.count('g')\n",
    "        num[6] = s.count('x')\n",
    "        num[7] = s.count('s')-num[6]\n",
    "        num[3] = s.count('h')-num[8]\n",
    "        num[4] = s.count('r')-num[3]-num[0]\n",
    "        num[1] = s.count('o')-num[4]-num[0]-num[2]\n",
    "        num[5] = s.count('f')-num[4]\n",
    "        num[9] = (len(s)-sum(num)*3-num[5]-num[7]*2-num[4]-num[3]*2-num[8]*2-num[0])//4\n",
    "        result = ''\n",
    "        for i in [0,1,2,3,4,5,6,7,8,9]:\n",
    "            result += str(i)*num[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num = [0 for i in range(10)]\n",
    "        s = list(s)\n",
    "        num[2] = s.count('w')\n",
    "        num[0] = s.count('z')\n",
    "        num[8] = s.count('g')\n",
    "        num[6] = s.count('x')\n",
    "        num[7] = s.count('s')-num[6]\n",
    "        num[3] = s.count('h')-num[8]\n",
    "        num[4] = s.count('r')-num[3]-num[0]\n",
    "        num[1] = s.count('o')-num[4]-num[0]-num[2]\n",
    "        num[5] = s.count('f')-num[4]\n",
    "        num[9] = (len(s)-sum(num)*3-num[5]-num[7]*2-num[4]-num[3]*2-num[8]*2-num[0])//4\n",
    "        result = ''\n",
    "        for i in range(10):\n",
    "            result += str(i)*num[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def originalDigits(self, s: str) -> str:\n",
    "        num = [0,0,0,0,0,0,0,0,0,0]\n",
    "        s = list(s)\n",
    "        num[2] = s.count('w')\n",
    "        num[0] = s.count('z')\n",
    "        num[8] = s.count('g')\n",
    "        num[6] = s.count('x')\n",
    "        num[7] = s.count('s')-num[6]\n",
    "        num[3] = s.count('h')-num[8]\n",
    "        num[4] = s.count('r')-num[3]-num[0]\n",
    "        num[1] = s.count('o')-num[4]-num[0]-num[2]\n",
    "        num[5] = s.count('f')-num[4]\n",
    "        num[9] = (len(s)-sum(num)*3-num[5]-num[7]*2-num[4]-num[3]*2-num[8]*2-num[0])//4\n",
    "        result = ''\n",
    "        for i in [0,1,2,3,4,5,6,7,8,9]:\n",
    "            result += str(i)*num[i]\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
